The present invention relates to a device for sorting data elements each including a respective sort key, comprising:
storage means organized according to a binary tree with 2.sup.n -1 nodes numbered from 1 to 2.sup.n -1 which are each able to contain a data element and are distributed in n successive stages numbered from 0 to n-1, whereby stage q comprises nodes 2.sup.q to 2.sup.q+1 -1; and PA1 means of control of the binary tree for dispersing the elements to be sorted within the tree in such a way as to satisfy an ordering condition according to which, for each integer i lying between 1 and 2.sup.n-1 -1 such that node i contains an element to be sorted, each of the nodes 2i and 2i+1 either contains no element to be sorted, or contains an element whose sort key is greater than or equal to, in the sense of a determined order relation, the sort key of the element contained in node i.
The ordering of the elements in the sort tree corresponds to what is referred to as a "heapsort" in the field of computerized sorting. In this regard, reference may be made to the work by Knuth: "The art of computer programming, Vol. 3, Sorting and searching", Addison Wesley, 1973, pages 142-157.
By way of illustration, FIG. 1 shows, in the case where n=4, a sort tree comprising fifteen nodes 1-15 containing data elements (of which only the sort key is represented) which satisfy the ordering condition.
Node 1 of stage 0 is referred to as the root or vertex of the tree. The 2.sup.n-1 nodes 2.sup.n-1 to 2.sup.n -1 of stage n-1 are referred to as leaves of the tree. For each node i of a stage q, the 2.sup.n-q -1 nodes of the tree whose numbers are of the form i2.sup.j +j', where j and j' are integers such that 0.ltoreq.j&lt;n-q and 0.ltoreq.j'&lt;2.sup.j, are referred to as descendants of node i (here, node i is considered to be included in its descendants). Among these descendants, the sister nodes 2i and 2i+1 of stage q+1 (if q&lt;n-1) are referred to as children of node i. The parent of node i (if q&gt;0) is on the other hand defined as that node of stage q-1 whose number is i/2 if i is even and (i-1)/2 if i is odd. These logic relations of parentage between the nodes of the tree are represented by arrows in FIG. 1.
The order relation between the sort keys is arbitrary. In the case illustrated in FIG. 1, it is the familiar order relation between the natural integers, allowing the sorting in ascending order of the sort keys. In the case of sorting in descending order, it is clearly sufficient to invert the order relation between the keys. In FIG. 1, the nodes of the tree which are not occupied by elements to be sorted are regarded as each containing an element whose sort key is infinite, that is to say greater than any sort key of a data element to be sorted. One possibility for coding an infinite key is to reserve one bit of the data field containing the key for this purpose; the key will for example be regarded as infinite if this bit is at 1 and as finite otherwise. In other words, this bit indicates whether the node is free or occupied by a data element.
Once it is loaded with a set of N&lt;2.sup.n ordered data elements, the sorting device is capable of delivering these N elements sequentially in N cycles in the order of the sort keys. The extracting of an element from the tree in the course of a cycle consists in reading the element located at the root of the tree and in tracing back elements of its descent in such a way as to always satisfy the ordering condition. Thus, in the case represented in FIG. 1, the first cycle consists in reading the element 16 located at the root, and in moving element 24 to the root, then element 38 to node 2 and finally element 623 to node 4. This amounts to propagating the extraction command from the root towards the leaves.
In some applications, it is necessary for the control means also to be capable of responding to commands for inserting a new element to be sorted into the tree. The sorting device is then capable of delivering or of receiving elements to be sorted at each cycle. It operates as a dynamic queue on the basis of the sort keys, managed according to the order relation used, and possibly representing time tags or any other type of priority index.
In known binary sort trees, the insertion command is not propagated from the root to the leaves of the tree since, at the level of the given node it is not known a priori to which of the two children the command is to be propagated, it being appreciated that the decendance of one of the two children may be completely filled and hence be inappropriate for receiving the command. The insertion command is therefore propagated from the leaves of the tree to the root. For example, to insert an element whose sort key is 28 into the tree of FIG. 1, it is written to a free leaf of the tree, for example leaf 9, and comparisons are made gradually with the elements contained in the higher nodes; thus, elements 28 and 38 will be interchanged in order to re-establish the ordering in the example considered.
Under these conditions, the preceding cycle has to be completed at the time that the element having the smallest key is extracted from the tree. Accordingly, the speed at which the device can deliver or receive data elements is limited by the duration of the cycle for processing a command, this being proportional to the number of stages n, i.e. to the logarithm of the maximum number N of elements to be sorted. In applications where this number N is large, for example a few thousand, and where high speed is required, for example greater than 500,000 elements per second, the sorting device can no longer be constructed with known electronic circuits.
In their article "A real time sorter with application to ATM traffic control" (Proc. ISS'95, April 1995, Volume 1, pages 258-262), J. W. Roberts et al. have described a sorting device which does not suffer from the above speed limitation, that is to say which is capable of delivering and receiving the elements at a rate which is a priori independent of the maximum number of elements to be sorted. However, a drawback of the latter device is that the number of logic circuits operating in parallel is proportional to N. Once the number N of elements to be sorted becomes large (a few thousand or tens of thousands as in the case of the application to an ATM cell spacer envisaged in the article), the hardware complexity of the device becomes prohibitive.
An object of the present invention is to propose a fast sorting device of limited complexity.